package DifficultPractice;

import java.util.Arrays;

public class Demo10 {
//	10. 正则表达式匹配
//	给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//
//	'.' 匹配任意单个字符
//	'*' 匹配零个或多个前面的那一个元素
//	所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
	public static void main(String[] args) {
		System.out.println(isMatch("ab", ".*c"));
	}
	
	private static int[][] memo;
	
	public static boolean isMatch(String s, String p) {
		memo = new int[s.length() + 1][p.length() + 1];
		for(int[] arr : memo) {
			Arrays.fill(arr, -1);
		}
		
        return dp(s, p, 0, 0);
    }
	
	private static boolean dp(String s, String p, int i, int j) {
		if(memo[i][j] != -1) {
			return (memo[i][j] != 0);
		}
		
		if(j == p.length()) {
			memo[i][j] = i == s.length() ? 1:0;
			return i >= s.length();
		}
		
			
		boolean res;
		//首次字符能否匹配？  注意&&之后的部分用括号括起来！
		boolean firstMatch = (i < s.length()) && ((s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.'));
		//看后面是否跟有*通配符
		if(j+1 < p.length() && p.charAt(j+1) == '*') {
			//发现通配符
			res = dp(s, p, i, j+2) || firstMatch && dp(s, p, i+1, j);
			//dp(s, p, i, j+2) ： 模式串替代了主串的0个字符，所以主串索引不动，模式串动两下
			//dp(s, p, i+1, j)：主串匹配上了一个字符，主串前进一下，模式串不动，看下一个主串字符能否再匹配上 
			//第二种情况必须要首字符匹配上的情况才能实现，所以firstMatch && dp(s, p, i+1, j)
		}
		else {
			res = firstMatch && dp(s, p, i+1, j+1);
		}
		memo[i][j] = res ? 1:0;
		return res;
		
	}
}
